package com.wunong.smart.algorithm.simple.greed;

/**
 * @author created by zealot.zt
 */
public class GreedUtils {

    /**
     * 硬币找零钱
     * 刚开始没有零钱，饮料5元/瓶，输入数据为n个，单位为元，对应值可以是5、10、20。现需要判断根据输入的数据，能否完成交易。
     *
     * 解题思路：
     * 1. 5元钱的数量最为通用，所以优先找10元
     * 2. 10元没有，找2-3个5元
     * 输入：
     * 5 10 5 20
     * 输出：
     * true
     *
     * @param array
     * @return
     */
    public static boolean coinChanges(int[] array) {
        if (array == null || array.length == 0) {
            return false;
        }

        // 5元钱数量
        int five = 0;
        // 10元钱数量
        int ten = 0;
        // 20元的数量
        int twenty = 0;

        for (int i = 0; i < array.length; i++) {
            if (array[i] == 5) {
                five++;
            } else if (array[i] == 10) {
                if (five <= 0) {
                    return false;
                }

                // 只能使用5元的找零
                five--;
                ten++;
            } else if (array[i] == 20) {
                // 一定会用到5元的
                if (five <= 0) {
                    return false;
                }

                // 此处优先判断是否有10元的
                if (ten > 0) {
                    ten--;
                    five--;
                    twenty++;
                } else if (five >= 3) {
                    five -= 3;
                    twenty++;
                } else {
                    return false;
                }
            }
        }

        return true;
    }

    private GreedUtils() {
    }

}
